package leetcode.code;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution240 implements IDebug {

	public boolean searchMatrix(int[][] matrix, int target) {
		int l = 0;
		int r = matrix.length - 1;
		int row = 0;
		while (l <= r) {
			int mid = ((r - l) >> 1) + l;
			if (matrix[mid][0] == target) {
				return true;
			} else if (target < matrix[mid][0]) {
				r = mid - 1;
			} else {
				row = mid;
				l = mid + 1;
			}
		}
		for (int i = row; i >= 0; i--) {
			l = 0;
			r = matrix[0].length - 1;
			while (l <= r) {
				int mid = ((r - l) >> 1) + l;
				if (matrix[i][mid] == target) {
					return true;
				} else if (target < matrix[i][mid]) {
					r = mid - 1;
				} else {
					l = mid + 1;
				}
			}
		}
		return false;
	}

	@Override
	public void debug1() {
		String str = "[[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]";
		int target = 5;
		boolean e = true;
		boolean r = this.searchMatrix(HelpDebug.str2array1(str), target);
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug2() {
		String str = "[[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]";
		int target = 20;
		boolean e = false;
		boolean r = this.searchMatrix(HelpDebug.str2array1(str), target);
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution240 so = new Solution240();
		so.debug1();
		so.debug2();

	}

}
